#暴力求解
class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        #强行输出n=1~4的结果
        if n == 0:
            return []
        elif n == 1:
            return ["()"]
        elif n ==2:
            return ["()()", "(())"]
        elif n ==3:
            return ["((()))","(()())","(())()","()(())","()()()"]
        elif n == 4:
            return ["()()()()","((()()))","()(())()","()((()))","()(()())","(()())()","(()(()))","((())())","((()))()","(())()()","()()(())","(()()())","(())(())","(((())))"]
        #初始化结果列表 res，将前面已知的结果硬编码放入 res 列表中，res[i] 表示 i 对括号时的合法组合列表。
        res = []
        res.append([])
        res.append(["()"])
        res.append(["()()", "(())"])
        res.append(["((()))","(()())","(())()","()(())","()()()"])
        res.append(["()()()()","((()()))","()(())()","()((()))","()(()())","(()())()","(()(()))","((())())","((()))()","(())()()","()()(())","(()()())","(())(())","(((())))"])
        #如果 n <= 4，直接从 res 中取出对应的结果，避免后续计算。
        if n <=4:
            return res[n]
        #如果 n >= 4，则从 res[4] 开始，依次计算 res[5]、res[6]、...、res[n]。
        #对于每个 res[i]，我们遍历 res[i-1] 中的每个字符串，并在每个字符串的每个位置插入一对括号，生成新的字符串，并将这些字符串加入 res[i] 中。
        for i in range(4, n):
            s = set()
            for k  in res[i]:
                for j in range(len(k)):
                    s.add(k[0:j] + '()' + k[j:] )
            res.append(list(s))
        return res[n]
